#include <iostream>
#include <vector>
#include <stack>
#include "lib/list.h"
#include "utils.h"

void swap(ListNode* node1, ListNode* node2) {
    int tmp = node1->value;
    node1->value = node2->value;
    node2->value = tmp;
}

// 拿第一个元素和后面的一个个比较，如果比后面的大就交换，
// 始终保证第一个元素是最小的。
void sort1(std::vector<int> &input) {
    int length = input.size();
    for (int i = 0; i < length - 1; i++) {
        for (int j = i + 1; j < length; j++) {
            if (input[i] > input[j]) {
                swap(input, i, j);
            }
        }
    }
}

// 相邻的两个比较，第一轮完成之后保证最后一个元素是最大的。
void sort2(std::vector<int> &input) {
    int length = input.size();
    for (int i = 1; i < length; i++) {
        for (int j = 0; j < length - i; j++) {
            if (input[j] > input[j + 1]) {
                swap(input, j, j + 1);
            }
        }
    }
}

// 如果后面已经排好序了，就不需要再比较了
void sort3(std::vector<int> &input) {
    int length = input.size();
    bool flag;
    for (int i = 1; i < length; i++) {
        flag = true;
        for (int j = 0; j < length - i; j++) {
            if (input[j] > input[j + 1]) {
                swap(input, j, j + 1);
                flag = false;
            }
        }
        if (flag == true)
            break;
    }
}

// 同sort3
void sort4(std::vector<int> &input) {
    int length = input.size();
    bool flag;
    for (int i = 1; i < length; i++) {
        flag = 0;
        for (int j = 0; j < length - i; j++) {
            if (input[j] > input[j + 1]) {
                swap(input, j, j + 1);
                flag = 1;
            }
        }
        if (flag == 0) {
            break;
        }
    }
}

// 递归写法
void sort5(std::vector<int> &input, int idx) {
    if (input.size() == 0 || idx == 1) {
        return;
    }
    int len = input.size();
    for (int i = 0; i < len - 1; i++) {
        if (input[i] > input[i + 1]) {
            swap(input, i, i + 1);
        }
    }
    sort5(input, idx - 1);
}

// 选择排序，默认前面是已经排好的，从后面选择最小的放在前面排好序的后面，
// 并不真正交换元素的位置，而是把未排序最小值的索引记录下来。
void sort6(std::vector<int> &input) {
    int len = input.size();
    for (int i = 0; i < len; i++) {
        int min_idx = i;
        for (int j = i + 1; j < len; j++) {
            if (input[j] < input[min_idx]) {
                min_idx = j;
            }
        }
        swap(input, i, min_idx);
    }
}

// 选择排序递归写法
void sort7(std::vector<int> &input, int idx) {
    if (input.size() == 0 || idx == input.size() - 1) {
        return;
    }
    int len = input.size();
    int min_idx = idx;
    for (int i = idx + 1; i < len; i++) {
        if (input[i] < input[min_idx]) {
            min_idx = i;
        }
    }
    swap(input, idx, min_idx);
    sort7(input, idx + 1);
}

// 插入排序：默认前面已经排好序了，从后面取出元素插入到合适的位置
void sort8(std::vector<int> &input) {
    if (input.size() < 2) {
        return;
    }
    for (int i = 1; i < input.size(); i++) {
        int key = input[i];
        int pos = i;
        for (int j = i - 1; j >= 0; j--) {
            if (input[j] > key) {
                input[j + 1] = input[j];
                pos--;
            } else {
                break;
            }
        }
        input[pos] = key;
    }
}

// 用二分法确定插入的位置
void sort9(std::vector<int> &input) {
    if (input.size() < 2) {
        return;
    }
    for (int i = 1; i < input.size(); i++) {
        if (input[i - 1] > input[i]) {
            int key = input[i];
            int low = 0;
            int high = i - 1;
            while (low <= high) {
                int middle = (low + high) >> 1;
                if (input[middle] > key) {
                    high = middle - 1;
                } else {
                    low = middle + 1;
                }
            }
            for (int j = i; j > low; j--) {
                input[j] = input[j - 1];
            }
            input[low] = key;
        }
    }
}

// 插入排序的递归写法
void sort10(std::vector<int> &input, int idx) {
    if (idx < 2) {
        return;
    }
    sort10(input, --idx);
    int key = input[idx];
    int j = idx;
    for (; j > 0; j--) {
        if (input[j - 1] > key) {
            input[j] = input[j - 1];
        } else {
            break;
        }
    }
    input[j] = key;
}

// 快速排序，选择一个中枢，小于它的往前放，大于它的往后放
void sort11(std::vector<int> &input, int start, int end) {
    if (start >= end) {
        return;
    }
    int key = input[start];
    int pos = start;
    for (int i = start + 1; i <= end; i++) {
        if (input[i] < key) {
            pos++;
            swap(input, pos, i);
        }
    }
    input[start] = input[pos];
    input[pos] = key;
    sort11(input, start, pos - 1);
    sort11(input, pos + 1, end);
}

int partition(std::vector<int> &input, int start, int end) {
    int pivot = input[start];
    while (start < end) {
        while (start < end && input[end] >= pivot) {
            end--;
        }
        swap(input, start, end);
        while (start < end && input[start] <= pivot) {
            start++;
        }
        swap(input, end, start);
    }
    return start;
}

// 快速排序
void sort12(std::vector<int> &input, int start, int end) {
    if (start >= end) {
        return;
    }
    int pivot = partition(input, start, end);
    sort12(input, start, pivot - 1);
    sort12(input, pivot + 1, end);
}

int partition1(std::vector<int> &input, int start, int end) {
    int pivot = start;
    while (start < end) {
        while(start < end && input[end] >= input[pivot]) {
            end--;
        }
        while(start < end && input[start] <= input[pivot]) {
            start++;
        }
        if (start < end) {
          swap(input, start, end);
        }
    }
    swap(input, start, pivot);
    return start;
}

// 快速排序
void sort13(std::vector<int> &input, int start, int end) {
    if (start >= end) {
        return;
    }
    int pivot = partition1(input, start, end);
    sort13(input, start, pivot - 1);
    sort13(input, pivot + 1, end);
}

// 快速排序的循环实现，用stack代替递归的栈
void sort14(std::vector<int> &input, int start, int end) {
    std::stack<int> stack_tmp;
    stack_tmp.push(end);
    stack_tmp.push(start);
    while (!stack_tmp.empty()) {
        int start = stack_tmp.top();
        stack_tmp.pop();
        int end = stack_tmp.top();
        stack_tmp.pop();
        int pvoit = partition(input, start, end);
        if (start < pvoit - 1) {
            stack_tmp.push(pvoit - 1);
            stack_tmp.push(start);
        }
        if (pvoit + 1 < end) {
            stack_tmp.push(end);
            stack_tmp.push(pvoit + 1);
        }
    }
}

// 用链表实现快速排序
void sort15(ListNode* start_node, ListNode* end_node) {
    if (start_node == end_node || start_node == nullptr || start_node == end_node->next) {
        return;
    }
    ListNode* pre_slow_ptr = start_node;
    ListNode* slow_ptr = start_node;
    ListNode* fast_ptr = start_node;
    while (fast_ptr != end_node) {
        fast_ptr = fast_ptr->next;
        if (fast_ptr->value < start_node->value) {
            pre_slow_ptr = slow_ptr;
            slow_ptr = slow_ptr->next;
            swap(slow_ptr, fast_ptr);
        }
    }
    swap(slow_ptr, start_node);
    sort15(start_node, pre_slow_ptr);
    sort15(slow_ptr->next, end_node);
}

// 归并排序（递归）
void merge(std::vector<int> &input, int start, int mid, int end) {
    std::vector<int> tmp;
    int left = start;
    int right = mid + 1;
    while (left <= mid && right <= end) {
        if (input[left] <= input[right]) {
            tmp.push_back(input[left++]);
        } else {
            tmp.push_back(input[right++]);
        }
    }
    while (left <= mid) {
        tmp.push_back(input[left++]);
    }
    while (right <= end) {
        tmp.push_back(input[right++]);
    }
    for (int i = 0; i < tmp.size(); i++) {
        input[start++] = tmp[i];
    }
}

void sort16(std::vector<int> &input, int start, int end) {
    if (start < end) {
        int mid = (start + end) >> 1;
        sort16(input, start, mid);
        sort16(input, mid + 1, end);
        merge(input, start, mid, end);
    }
}

// 归并排序（循环）
void sort17(std::vector<int> &input) {
    int len = input.size();
    for (int i = 1; i < len; i = i << 1) {
        for (int j = 0; j + i < len; j += 2 * i) {
            merge(input, j, j + i - 1, std::min(j + 2 * i - 1, len - 1));
        }
    }
}

// 堆排序
void adjustHead(std::vector<int> &input, int start, int end) {
    int left_node = start * 2 + 1;
    int right_node = start * 2 + 2;
    int larger_node = start;
    if (left_node < end && input[left_node] > input[start]) {
        larger_node = left_node;
    }
    if (right_node < end && input[right_node] > input[larger_node]) {
        larger_node = right_node;
    }
    if (larger_node != start) {
        swap(input, start, larger_node);
        adjustHead(input, larger_node, end);
    }
}

void buildHead(std::vector<int> &input) {
    int size = input.size();
    // 非叶子结点
    // 从后往前排，否则后面的可能比前面的大
    for (int i = size / 2 - 1; i >= 0; i--) {
        adjustHead(input, i, size);
    }
}

void headSort(std::vector<int> &input) {
    int size = input.size();
    buildHead(input);
    for (int i = 0; i < input.size(); i++) {
        swap(input, 0, size - i - 1);
        adjustHead(input, 0, size - i - 1);
    }
}

// 桶排序，自定义桶大小
void bucketSort(std::vector<int> &input, int bucket_size) {
    int size = input.size();
    int min_val = input[0];
    int max_val = input[0];
    for (int i = 1; i < size; i++) {
        if (input[i] < min_val) {
            min_val = input[i];
        }
        if (input[i] > max_val) {
            max_val = input[i];
        }
    }
    int bucket_count = (max_val - min_val) / bucket_size + 1;

    // 初始化二维数组
    std::vector<std::vector<int>> buckets;
    for (int i = 0; i < bucket_count; i++) {
        std::vector<int> bucket;
        buckets.push_back(bucket);
    }

    for (int i = 0; i < size; i++) {
        int bucket_idx = (input[i] - min_val) / bucket_size;
        buckets[bucket_idx].push_back(input[i]);
    }

    input.clear();
    for (int i = 0; i < bucket_count; i++) {
        // 随便用一种排序算法给每个桶排序
        std::sort(buckets[i].begin(), buckets[i].end());
        for (int j = 0; j < buckets[i].size(); j++) {
            input.push_back(buckets[i][j]);
        }
    }
}

// 基数排序，先排个位，再排十位，再排百位......
int getBitCount(int num) {
    int count = 0;
    while (num) {
        count++;
        num /= 10;
    }
    return count;
}

// 找绝对值的最大值，用于处理负数
int getMaxNum(std::vector<int> input) {
    int min_val = input[0];
    int max_val = input[0];
    for (int i = 1; i < input.size(); i++) {
        if (input[i] < min_val) {
            min_val = input[i];
        }
        if (input[i] > max_val) {
            max_val = input[i];
        }
    }
    return max_val < -min_val ? -min_val : max_val;
}

void radixSort(std::vector<int> &input) {
    int digit_count = 19; // -9到9，用于处理负数
    int max_count = getBitCount(getMaxNum(input));
    int radix = 1;

    // 行表示0-19的第几个数，列表示这个数在input里出现了几次
    // TODO: 初始化temp_vec，有没有更好的写法？
    std::vector<std::vector<int>> temp_vec;
    for (int i = 0; i < digit_count; i++) {
        std::vector<int> tmp;
        temp_vec.push_back(tmp);
    }

    for (int i = 0; i < max_count; i++) {
        // temp_vec和count置零
        for (int i = 0; i < temp_vec.size(); i++) {
            temp_vec[i].clear();
        }
        std::vector<int> count(digit_count, 0);

        for (int j = 0; j < input.size(); j++) {
            int idx = (input[j] / radix) % 10 + 9; //把-9到9映射到0到19
            temp_vec[idx].push_back(input[j]);
            count[idx]++;
        }

        int index = 0;
        for (int j = 0; j < digit_count; j++) {
            if (count[j] == 0) {
                continue;
            }
            for (int k = 0; k < count[j]; k++) {
                input[index++] = temp_vec[j][k];
            }
        }
        radix *= 10;
    }
}

// 希尔排序，step喜欢用step = step * 3 + 1?
void shellSort(std::vector<int> &input) {
    int size = input.size();
    int step = size;
    while (step > 1) {
        step = step / 3 + 1;
        for (int i = step; i < size; i++) {
            int tmp = input[i];
            int j = i - step;
            while (j >= 0 && input[j] > tmp) {
                input[j + step] = input[j];
                j -= step;
            }
            input[j + step] = tmp;
        }
    }
}

// 计数排序
void countSort(std::vector<int> &input) {
    int size = input.size();
    int min_val = input[0];
    int max_val = input[0];
    for (int i = 1; i < size; i++) {
        if (input[i] < min_val) {
            min_val = input[i];
        }
        if (input[i] > max_val) {
            max_val = input[i];
        }
    }
    int bucket_size = max_val - min_val + 1;
    std::vector<int> bucket(bucket_size, 0);
    for (int i = 0; i < size; i++) {
        int idx = input[i] - min_val;
        bucket[idx]++;
    }
    for (int i = 1; i < size; i++) {
        bucket[i] += bucket[i - 1];
    }
    std::vector<int> tmp(input);
    for (int i = 0; i < size; i++) {
        int idx = tmp[i] - min_val;
        input[--bucket[idx]] = tmp[i];
    }
}

// 位图排序，用于海量数据去重和海量数据排序，排序时数据不能有重复
void bitmapSort(std::vector<int> &input) {
    int size = input.size();
    int min_val = input[0];
    int max_val = input[0];
    for (int i = 1; i < size; i++) {
        if (input[i] < min_val) {
            min_val = input[i];
        }
        if (input[i] > max_val) {
            max_val = input[i];
        }
    }
    int sort_count = (max_val - min_val + 1) / 64 + 1;
    std::vector<long> sort_num(sort_count, 0);
    for (int i = 0; i < size; i++) {
        int sort_div = (input[i] - min_val) / 64;
        int sort_mod = (input[i] - min_val) % 64;
        sort_num[sort_div] |= (1L << sort_mod);
    }
    input.clear();
    for (int i = min_val; i <= max_val; i++) {
        int div = (i - min_val) / 64;
        int mod = (i - min_val) % 64;
        if (sort_num[div] & (1L << mod)) {
            input.push_back(i);
        }
    }
}

// 鸡尾酒排序，类似冒泡排序，往两个方向排
void cocktailSort(std::vector<int> &input) {
    int left = 0;
    int right = input.size() - 1;
    while (left < right) {
        for (int i = left; i < right; i++) {
            if (input[i] > input[i + 1]) {
                swap(input, i, i + 1);
            }
        }
        right--;
        for (int i = right; i > left; i--) {
            if (input[i] < input[i - 1]) {
                swap(input, i, i - 1);
            }
        }
        left++;
    }
}

// 鸽巢排序，没看出来和计数排序有什么区别
void pigeonholeSort(std::vector<int> &input) {
    int size = input.size();
    int min_val = input[0];
    int max_val = input[0];
    for (int i = 1; i < size; i++) {
        if (input[i] < min_val) {
            min_val = input[i];
        }
        if (input[i] > max_val) {
            max_val = input[i];
        }
    }
    int num_count = max_val - min_val + 1;
    std::vector<int> bucket(num_count, 0);
    for (int i = 0; i < size; i++) {
        int idx = input[i] - min_val;
        bucket[idx]++;
    }
    int index = 0;
    for (int i = min_val; i <= max_val; i++) {
        for (int j = 0; j < bucket[i - min_val]; j++) {
            input[index++] = i;
        }
    }
}

int main() {
    std::vector<int> input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    printVec("input", input);

    sort1(input);
    printVec("sort1", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort2(input);
    printVec("sort2", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort3(input);
    printVec("sort3", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort4(input);
    printVec("sort4", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort5(input, input.size());
    printVec("sort5", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort6(input);
    printVec("sort6", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort7(input, 0);
    printVec("sort7", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort8(input);
    printVec("sort8", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort9(input);
    printVec("sort9", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort10(input, input.size());
    printVec("sort10", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort11(input, 0, input.size() - 1);
    printVec("sort11", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort12(input, 0, input.size() - 1);
    printVec("sort12", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort13(input, 0, input.size() - 1);
    printVec("sort13", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort14(input, 0, input.size() - 1);
    printVec("sort14", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    ListNode* start_node = CreateList(input);
    ListNode* end_node = start_node;
    while (end_node->next) {
        end_node = end_node->next;
    }
    sort15(start_node, end_node);
    std::cout << "[sort15]: ";
    PrintList(start_node);
    DeleteList(start_node);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort16(input, 0, input.size() - 1);
    printVec("sort16", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    sort17(input);
    printVec("sort17", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    headSort(input);
    printVec("headSort", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    bucketSort(input, 2);
    printVec("bucketSort", input);

    input = {12, 345, 677, 238, -2354, 93, 10, 39, 246};
    radixSort(input);
    printVec("radixSort", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    shellSort(input);
    printVec("shellSort", input);

    input = {2, 5, 7, 8, 4, 3, 1, 9, 6};
    countSort(input);
    printVec("countSort", input);

    input = {12, 345, 677, 238, -2354, 93, 10, 39, 246};
    bitmapSort(input);
    printVec("bitmapSort", input);

    input = {12, 345, 677, 238, -2354, 93, 10, 39, 246};
    cocktailSort(input);
    printVec("cocktailSort", input);

    input = {12, 345, 677, 238, -2354, 93, 10, 39, 246};
    pigeonholeSort(input);
    printVec("pigeonholeSort", input);

    return 0;
}
